package backtrackStudy;

public class SolveSudoku {

    /**
     * 回溯法——棋盘问题之数独
     * LeetCode T37 解数独
     * 编写一个程序，通过填充空格来解决数独问题。
     *
     * 数独的解法需 遵循如下规则：
     *
     * 数字 1-9 在每一行只能出现一次。
     * 数字 1-9 在每一列只能出现一次。
     * 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
     * 数独部分空格内已填入了数字，空白格用 '.' 表示。
     *
     * @param args
     */
    public static void main(String[] args) {

    }

    public static void solveSudoku(char[][] board){
        backtrace(board, 0, -1, new boolean[]{false});
    }

    //通过暴力回溯解决棋盘问题
    //首先确定返回值和参数
    public static void backtrace(char[][] board, int m, int n, boolean[] b){
        int len = board.length;
        //遍历得到下一个需要处理的节点
        while (true){
            n++;
            if (n >= len){
                n = n % len;
                m++;
            }
            if (m >= len){
                break;
            } else {
                if (board[m][n] == '.'){
                    break;
                }
            }
        }
        //定义出口
        if (m >= len){
            b[0] = true;
            return;
        }

        //循环体
        for (int i = 1; i <= len; i++){
            boolean flag = false;
            //确定选择列表，即排除重复元素
            //排除行元素
            for (int x = 0; x < len && !flag; x++){
                if (board[m][x] == 48 + i){
                    //存在相等元素
                    flag = true;
                    break;
                }
            }
            //排除列元素
            for (int y = 0; y <= len && !flag; y++){
                if (board[y][n] == 48 + i){
                    flag = true;
                    break;
                }
            }
            //排除方格元素
            int rowBegin = (m/3)*3;
            int columnBegin = (n/3)*3;
            for (int x = 0; x < 3 && !flag; x++){
                for (int y = 0; y < 3 && !flag; y++){
                    if (board[rowBegin+x][columnBegin+y]== 48+i){
                        flag = true;
                        break;
                    }
                }
            }
            if (flag){
                continue;
            }
            //选择
            board[m][n] = (char) (i + 48);
            backtrace(board, m, n, b);
            //取消选择
            if (b[0]){
                return;
            }
            board[m][n] = '.';
        }

    }
}
